package Array;

public class 柱状图中最大的矩形 {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] leftMin = new int[len];
        int[] rightMin = new int[len];
        leftMin[0] = -1;
        rightMin[len - 1] = len;
        int maxArea = 0;
        for (int i = 1; i < len; i++) {
            int left = i - 1;
            while (left >= 0 && heights[left] >= heights[i]) left = leftMin[left];
            leftMin[i] = left;
        }
        for (int i = len - 2; i >= 0; i--) {
            int right = i + 1;
            while (right < len && heights[right] >= heights[i]) right = rightMin[right];
            rightMin[i] = right;
        }
        for (int i = 0; i < len; i++) {
            int area = heights[i] * (rightMin[i] - leftMin[i] - 1);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }
}
